Introduction to Machine Learning

Unit 16: Linear Regression: Analytical and Gradient Descent

1. Introduction

This unit introduces Linear Regression, one of the most fundamental and widely used algorithms in machine learning and statistics. We will learn how to fit a line (or hyperplane) to data using two complementary approaches: the analytical closed-form solution (Normal Equation) and the iterative Gradient Descent algorithm. By the end of this unit, you will understand when to use each method and be able to derive and implement both from first principles.

Learning Objectives

2. Theory

2.1 What is Linear Regression?

The goal of linear regression is to model the relationship between one or multiple features and a continuous target variable. Given data points \( (x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m) \), we find a line (or hyperplane) that "best fits" the data.

Simple Linear Regression (1 Feature)

\[ \hat{y} = w_1 x + b \]

Example: Car Fuel Efficiency

Suppose we want to predict a car's fuel efficiency (miles per gallon) based on how heavy the car is. A learned model might have:

Pounds (in 1000s)Miles per Gallon
3.5018
3.6915
3.4418
3.4316
4.3415
4.4214
2.3724

2.2 Multiple Linear Regression

A model that predicts gas mileage could additionally use features such as engine displacement (\( x_2 \)), acceleration (\( x_3 \)), number of cylinders (\( x_4 \)), and horsepower (\( x_5 \)). The equation becomes:

\[ y = b + w_1 x_1 + w_2 x_2 + w_3 x_3 + w_4 x_4 + w_5 x_5 \]

2.3 Two Approaches for Finding Optimal Parameters

Approach 1: Analytical (Closed-form)
Approach 2: Gradient Descent (Iterative)

2.4 The Cost Function: Mean Squared Error (MSE)

To measure how "wrong" our predictions are, we use the Mean Squared Error (MSE), also known as the squared loss. For a model with parameters \( \theta \) (where \( \theta_0 = b \) is the bias and \( \theta_1, \ldots \) are weights):

\[ J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} \left( h_\theta(x_i) - y_i \right)^2 \]

The \( \frac{1}{2} \) factor is a convenience that cancels the 2 from differentiation (you will see this shortly). Minimizing \( \frac{1}{2} \text{MSE} \) is equivalent to minimizing MSE — the optimal \( \theta \) is the same.

Matrix Notation for Multiple Variables

Let \( X \) be the \( m \times (p+1) \) design matrix (with a column of 1's prepended for the bias), \( \theta \) the \( (p+1) \times 1 \) parameter vector, and \( y \) the \( m \times 1 \) target vector. Predictions are \( \hat{y} = X\theta \), and MSE becomes:

\[ J(\theta) = \frac{1}{2m} (X\theta - y)^T (X\theta - y) \]

Here \( (X\theta - y)^T \) is \( 1 \times m \), \( (X\theta - y) \) is \( m \times 1 \), and their product is a \( 1 \times 1 \) scalar — exactly like the sum of squared residuals.

2.5 Analytical Solution: The Normal Equation

To find the \( \theta \) that minimizes \( J(\theta) \), we take the derivative with respect to \( \theta \), set it to zero, and solve algebraically.

\[ \frac{\partial J}{\partial \theta} = \frac{1}{m} \left( X^T X \theta - X^T y \right) = 0 \]

Rearranging gives the Normal Equation:

\[ \theta = \left( X^T X \right)^{-1} X^T y \]

Drawbacks of the Analytical Solution

DrawbackExplanation
Computational Complexity Matrix inversion is \( O(n^3) \). For \( n = 10{,}000 \) features, ~1 trillion operations!
Non-Invertible Matrix \( X^T X \) might be singular if features are linearly dependent or \( m \lt p \).
Memory Requirements Must store the entire dataset in memory; \( X^T X \) is \( (p+1) \times (p+1) \).
No Generalization Only works for this specific problem — cannot extend to NNs, logistic regression, etc.

2.6 Gradient Descent: The Big Picture

Gradient Descent is a mathematical technique that iteratively finds the weights and bias that produce the model with the lowest loss. The model begins with randomized weights and biases (usually near zero), then repeats the following process:

  1. Calculate the loss \( J(\theta) \) with the current parameters.
  2. Determine the direction to move the parameters that reduces loss (this is the negative of the gradient vector).
  3. Move the parameter values a small amount in that direction (scaled by the learning rate \( \alpha \)).
  4. Return to step 1 until the loss plateaus (stops decreasing significantly).
Gradient descent toward a global minimum A cost function J of theta with a starting point on a downhill slope leading toward the global minimum. J(θ) θ Start here Global minimum α·∇J step toward lower cost

2.7 Gradient Descent for Simple Linear Regression

For the simple model \( h_\theta(x) = \theta_0 + \theta_1 x \), we need the partial derivatives of \( J \) with respect to both \( \theta_0 \) and \( \theta_1 \).

\begin{align} \frac{\partial J}{\partial \theta_0} &= \frac{1}{m} \sum_{i=1}^{m} \left( \theta_0 + \theta_1 x_i - y_i \right) \\ \frac{\partial J}{\partial \theta_1} &= \frac{1}{m} \sum_{i=1}^{m} \left( \theta_0 + \theta_1 x_i - y_i \right) x_i \end{align}

The update rules (simultaneous update!) are:

\begin{align} \theta_0 &:= \theta_0 - \alpha \frac{\partial J}{\partial \theta_0} \\ \theta_1 &:= \theta_1 - \alpha \frac{\partial J}{\partial \theta_1} \end{align}

Algorithm Steps

  1. Initialize: Set \( \theta_0, \theta_1 \) to 0 or small random numbers.
  2. Compute Predictions: For all data points, calculate \( h_\theta(x_i) \).
  3. Compute Gradients: Use the formulas above.
  4. Update Parameters (simultaneously, using the old gradients for BOTH updates).
  5. Loop: Repeat steps 2–4 for many iterations (e.g., 1000) or until \( J \) stops decreasing significantly. Always track \( J \) over iterations to ensure it's minimizing!

2.8 Gradient Descent for Multiple Linear Regression

The multivariate case is a direct extension. With \( h_\theta(x) = \theta^T x = \sum_{j=0}^{p-1} \theta_j x_j \) (where \( x_0 = 1 \)):

\[ \frac{\partial J}{\partial \theta_j} = \frac{1}{m} \sum_{i=1}^{m} \left( \theta^T x_i - y_i \right) x_{i,j} \]

In matrix form, the entire gradient vector is:

\[ \nabla J(\theta) = \frac{1}{m} X^T (X\theta - y) \]

And the compact vectorized update:

\[ \theta := \theta - \alpha \nabla J(\theta) \]

3. Interactive Examples

Example 1: Interpret Slope and Intercept

A fitted regression model for house price (in $1000s) on house size (in 100s of sq ft) is: \( \hat{y} = 50 + 35x \). Click to reveal interpretations.

A. Interpret the intercept \( \theta_0 = 50 \).

A house with zero square footage (not realistic!) is predicted to cost $50,000. More practically: the intercept anchors the line at $50K when size = 0. For sizes within the data range, it simply shifts the whole line up/down.

B. Interpret the slope \( \theta_1 = 35 \).

Each additional 100 sq ft of house size is associated with an average increase of $35,000 in predicted house price.

C. Predict the price of a 1,500 sq ft house. (Watch units! \( x \) is in 100s of sq ft.)

1,500 sq ft → \( x = 15 \). Then:
\[ \hat{y} = 50 + 35(15) = 50 + 525 = \mathbf{\$575{,}000} \]

Example 2: Analytical vs. Iterative — Which to Use?

For each scenario, pick the better approach: Normal Equation or Gradient Descent.

Scenario A: 500 training examples, 3 features, need answer quickly for a statistics homework.

Normal Equation. With only 3 features, inversion of a 4×4 matrix is trivial. You get the exact answer in one line of linear algebra.

Scenario B: 5,000,000 training examples, 500 features, training on GPU with TensorFlow.

Gradient Descent. Inverting a 501×501 matrix is possible, but GD is far more memory-efficient and scalable. It also generalizes — the same code template will work for logistic regression and neural networks.

Example 3: Spot the Bug in GD Code Logic

A student writes the following update step. What's wrong?

temp0 = θ0 − α · dJ/dθ0
θ0    = temp0
temp1 = θ1 − α · dJ/dθ1   ← dJ/dθ1 uses the ALREADY-UPDATED θ0
θ1    = temp1
Simultaneous update violated! The gradient for \( \theta_1 \) must be computed using the old value of \( \theta_0 \) (from before this iteration began). The student updated \( \theta_0 \) first, which pollutes the gradient of \( \theta_1 \). Fix: store both partial derivatives in temporary variables, then apply both updates at once.

4. Numerical Solutions

Problem 1: Single-Step Gradient Descent on Tiny Data

Given one training example \( (x = 2, y = 7) \), current parameters \( \theta_0 = 1 \), \( \theta_1 = 2 \), and learning rate \( \alpha = 0.1 \).

📘 Step-by-Step Solution

Step 1: Compute the prediction \( \hat{y} = h_\theta(x) \).

\[ \hat{y} = \theta_0 + \theta_1 x = 1 + 2(2) = 5 \]

Step 2: Compute the error \( \hat{y} - y = 5 - 7 = -2 \).

Step 3: Compute gradients (with \( m = 1 \)):

\begin{align} \frac{\partial J}{\partial \theta_0} &= \frac{1}{1} (\hat{y} - y) \cdot 1 = -2 \\ \frac{\partial J}{\partial \theta_1} &= \frac{1}{1} (\hat{y} - y) \cdot x = -2 \cdot 2 = -4 \end{align}

Step 4: Apply the simultaneous update with \( \alpha = 0.1 \):

\begin{align} \theta_0 &:= 1 - 0.1(-2) = 1 + 0.2 = \mathbf{1.2} \\ \theta_1 &:= 2 - 0.1(-4) = 2 + 0.4 = \mathbf{2.4} \end{align}

Notice that the error was negative (we under-predicted), so both parameters move in the positive direction, which is the correct "uphill" push to raise predictions closer to \( y = 7 \).

Problem 2: MSE Cost Calculation

Compute \( \frac{1}{2} \text{MSE} \) (i.e., \( J(\theta) \)) for the dataset:

i\( x_i \)\( y_i \)\( \hat{y}_i = 1 + 2x_i \)
1143
2275
3387
📘 Step-by-Step Solution

Step 1: Compute residuals \( r_i = \hat{y}_i - y_i \):

  • \( r_1 = 3 - 4 = -1 \)
  • \( r_2 = 5 - 7 = -2 \)
  • \( r_3 = 7 - 8 = -1 \)

Step 2: Sum of squared residuals:

\[ \sum_{i=1}^{3} r_i^2 = (-1)^2 + (-2)^2 + (-1)^2 = 1 + 4 + 1 = 6 \]

Step 3: Divide by \( 2m = 6 \):

\[ J(\theta) = \frac{6}{6} = \mathbf{1.0} \]

Problem 3: Normality Check — Invertible \( X^T X \)?

Design matrix \( X \) (with bias column): \( X = \begin{bmatrix} 1 & 1 & 2 \\ 1 & 2 & 4 \\ 1 & 3 & 6 \end{bmatrix} \). Column 3 is exactly 2 × Column 2.

📘 Step-by-Step Discussion

Step 1: Recognize linear dependence. Column 3 = 2 · Column 2.

Step 2: Conclude \( X^T X \) is singular (non-invertible).

\[ X^T X = \begin{bmatrix} 3 & 6 & 12 \\ 6 & 14 & 28 \\ 12 & 28 & 56 \end{bmatrix} \implies \text{Col}_3 = 2 \cdot \text{Col}_2 \implies \det = 0 \]

Step 3: Remedies:

  1. Feature removal: Drop one of the two linearly dependent columns (they carry the same information).
  2. Ridge Regression: Add \( \lambda I \) to \( X^T X \) before inverting (see Unit 18!) — regularization guarantees invertibility.
  3. Gradient Descent: Avoid matrix inversion entirely — GD still works (though the solution won't be unique without regularization).

5. Try It Yourself

Problem 1 — Gradient Descent One Step

With \( m = 2 \) examples: \( (x=1, y=3) \) and \( (x=3, y=7) \). Current parameters: \( \theta_0 = 0 \), \( \theta_1 = 1 \). Learning rate \( \alpha = 0.05 \).

  1. Compute predictions \( \hat{y}_1, \hat{y}_2 \).
  2. Compute both partial derivatives.
  3. Apply the GD update to find the new \( \theta_0, \theta_1 \).

Predictions: \( \hat{y}_1 = 0 + 1(1) = 1 \), \( \hat{y}_2 = 0 + 1(3) = 3 \).

Residuals: \( r_1 = 1 - 3 = -2 \), \( r_2 = 3 - 7 = -4 \).

\begin{align} \frac{\partial J}{\partial \theta_0} &= \tfrac{1}{2}(-2 + -4) = -3 \\ \frac{\partial J}{\partial \theta_1} &= \tfrac{1}{2}(-2 \cdot 1 + -4 \cdot 3) = \tfrac{1}{2}(-14) = -7 \end{align}
\begin{align} \theta_0 &:= 0 - 0.05(-3) = \mathbf{+0.15} \\ \theta_1 &:= 1 - 0.05(-7) = \mathbf{1.35} \end{align}
Problem 2 — Normal Equation Dimensions

A dataset has \( m = 1200 \) training examples and \( p = 8 \) features (plus the bias column). State the dimensions of:

  1. Design matrix \( X \)
  2. Target vector \( y \)
  3. Parameter vector \( \theta \)
  4. \( X^T X \) (the matrix being inverted)
  5. Final \( \theta \) after Normal Equation
  1. \( X \): \( 1200 \times 9 \) (rows = examples, cols = bias + 8 features)
  2. \( y \): \( 1200 \times 1 \)
  3. \( \theta \): \( 9 \times 1 \)
  4. \( X^T X \): \( 9 \times 9 \) (this is why inversion is cheap!) — \( X^T \) is \( 9 \times 1200 \), times \( X \) \( 1200 \times 9 \)
  5. \( \theta \): \( 9 \times 1 \) (same parameters, now optimal values)
Problem 3 — Learning Rate Intuition

Match each GD behavior (left) to the likely learning-rate issue (right):

  1. Cost \( J \) oscillates wildly, actually increasing each epoch → ?
  2. Cost \( J \) decreases for 50 epochs then crawls, never reaching the minimum after 10,000 epochs → ?
  3. Cost \( J \) decreases smoothly, plateaus after ~400 epochs → ?

Answers pool: (a) α too small, (b) α well-tuned, (c) α too large / diverging

  1. → (c) α too large — steps overshoot the minimum and bounce away.
  2. → (a) α too small — each step is tiny; convergence is glacially slow.
  3. → (b) α well-tuned — healthy training curve.

6. Interactive Quiz

Your score: 0 / 5

7. Key Takeaways

  1. Linear model form: Simple regression: \( \hat{y} = \theta_0 + \theta_1 x \). Multiple regression: \( \hat{y} = \theta^T x \) (with \( x_0 = 1 \)). Always add the bias column explicitly in matrix code.
  2. MSE cost: \( J(\theta) = \frac{1}{2m} \sum (\hat{y}_i - y_i)^2 \). The \( \frac{1}{2} \) cancels the 2 from differentiation — a standard convention, not a bug.
  3. Normal Equation: \( \theta = (X^T X)^{-1} X^T y \). Exact, one-shot, O(p³). Fails when features are collinear or memory is tight.
  4. Gradient Descent: \( \theta := \theta - \alpha \nabla J \). Works for any differentiable loss (not just MSE). Scales to millions of examples via mini-batches.
  5. Simultaneous updates only: Never interleave gradient computation and parameter updates within one iteration — compute all gradients first, then apply all updates.
  6. Learning rate α is critical: Too small → glacial convergence; too large → divergence / oscillation. Always plot J(θ) vs. iteration to diagnose.

8. Common Pitfalls

  1. Forgetting the bias column (x₀ = 1) in the design matrix. The Normal Equation or matrix-form GD will silently produce wrong results because \( \theta_0 \) has no "feature" to multiply. Always prepend a column of ones.
  2. Using the Normal Equation blindly when XᵀX is singular. Multicollinearity (linearly dependent features) or \( m \lt p \) causes inversion to fail. Fix with feature removal or Ridge regularization, not by "adding a tiny number to the diagonal" ad-hoc.
  3. Updating θ₀ then using the new θ₀ in the gradient of θ₁ within the same iteration. This breaks the simultaneous-update contract and produces incorrect convergence paths. Use temp variables.
  4. Assuming MSE = J(θ) by the numbers. \( J = \frac{1}{2} \text{MSE} \). When a library reports "MSE," multiply by \( \frac{m}{2} \) (or compare trends, not absolute values) to match the in-class formulas.
  5. Feature scaling ignored for Gradient Descent. Without standardization, a feature in the range 0–10,000 will dominate the gradient updates, producing an elongated cost bowl with zig-zagging convergence. We'll formalize this in Unit 17.
  6. Running GD for a fixed number of epochs with no cost monitoring. Always record and plot \( J(\theta) \) during training to detect divergence (α too big) or early plateau (good stop / α too small).

9. Resources